package algorithm.leetcode.I1to100;

import java.util.Arrays;

/**
 * 没什么意思
 * 背答案就行
 *
 * 算法流程
 * 1. 从后向前查找第一个相邻升序的元素对 (i,i+1)，满足 A[i] < A[i+1]。此时 [i+1,end) 必然是降序
 * 2. 在 [i+1,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
 * 3. 将 A[i] 与 A[k] 交换
 * 4. 可以断定这时 [i+1,end) 必然是降序，逆置 [i+1,end)，使其升序
 * 5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
 *
 *
 */

public class Q31 {

    public void nextPermutation(int[] nums) {
        if (nums.length == 1) return;

        // 步骤1:逆向找到第一个升序元素对
        int i = nums.length-2, j = nums.length-1;
        while (i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }

        // 步骤2:
        // 只要不是完全逆序
        if (i >= 0) {
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }

            // 步骤3:
            swapInPlace(nums, j, i);
        }

        // 步骤4:从i+1到nums.length-1执行reverse
        j = nums.length-1;
        i++;
        while (i < j) {
            swapInPlace(nums, i++, j--);
        }

    }

    public static void swapInPlace(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public static void main(String[] args) {
        Q31 q31 = new Q31();
        int[] ints = {1,3,3};
        q31.nextPermutation(ints);
        System.out.println(Arrays.toString(ints));
    }

}
